import sys
sys.setrecursionlimit(2147483647)
MOD = 1000000007
input = sys.stdin.readline
s = input().strip()
n = len(s)
memo = {}
def dp(i,prev):
if (i,prev) in memo:
return memo[(i,prev)]
if i==n:
return 1
nxt = int(s[i])+prev
if nxt%2==0:
memo[(i,prev)] = dp(i+1,nxt//2)
else:
memo[(i,prev)] = dp(i+1,nxt//2) + dp(i+1,nxt//2+1)
return memo[(i,prev)]
ans = 0
for i in range(0,10):
ans += dp(1,i)
def check(i,cur):
if int(s[i])!=cur:
return False
if i==n-1:
return True
nxt = int(s[i+1])+(cur)
if nxt%2==0:
return check(i+1,nxt//2)
else:
if int(s[i+1])==nxt//2:
return check(i+1,nxt//2)
elif int(s[i+1])==nxt//2+1:
return check(i+1,nxt//2+1)
else:
return False
if check(0,int(s[0])):
print(ans-1)
else:
print(ans)
//f[i+1][(j+(s[i+1]-'0'))/2]+=f[i][j];
//if((j+(s[i+1]-'0'))%2)
// f[i+1][(j+(s[i+1]-'0'))/2+1]+=f[i][j];
//i=当前位置,j=当前数字,f[i][j]=当前种类
#include<bits/stdc++.h>
using namespace std;
long long ba;
long long f[55][15];
string s;
bool check()
{
for(long long i=1;i<s.size();i++)
{
if(abs(s[i]-s[i-1])>1)
return 0;
}
return 1;
}
int main()
{
cin>>s;
for(long long i=0;i<10;i++)
f[0][i]=1;
for(long long i=0;i<s.size()-1;i++)
for(long long j=0;j<10;j++)
{
f[i+1][(j+(s[i+1]-'0'))/2]+=f[i][j];
if((j+(s[i+1]-'0'))%2)
f[i+1][(j+(s[i+1]-'0'))/2+1]+=f[i][j];
}
for(long long i=0;i<10;i++)
ba+=f[s.size()-1][i];
if(check())
cout<<ba-1;
else
cout<<ba;
return 0;
}1351. Count Negative Numbers in a Sorted Matrix | 617. Merge Two Binary Trees |
1450. Number of Students Doing Homework at a Given Time | 700. Search in a Binary Search Tree |
590. N-ary Tree Postorder Traversal | 589. N-ary Tree Preorder Traversal |
1299. Replace Elements with Greatest Element on Right Side | 1768. Merge Strings Alternately |
561. Array Partition I | 1374. Generate a String With Characters That Have Odd Counts |
1822. Sign of the Product of an Array | 1464. Maximum Product of Two Elements in an Array |
1323. Maximum 69 Number | 832. Flipping an Image |
1295. Find Numbers with Even Number of Digits | 1704. Determine if String Halves Are Alike |
1732. Find the Highest Altitude | 709. To Lower Case |
1688. Count of Matches in Tournament | 1684. Count the Number of Consistent Strings |
1588. Sum of All Odd Length Subarrays | 1662. Check If Two String Arrays are Equivalent |
1832. Check if the Sentence Is Pangram | 1678. Goal Parser Interpretation |
1389. Create Target Array in the Given Order | 1313. Decompress Run-Length Encoded List |
1281. Subtract the Product and Sum of Digits of an Integer | 1342. Number of Steps to Reduce a Number to Zero |
1528. Shuffle String | 1365. How Many Numbers Are Smaller Than the Current Number |